# 505. 数字三角形
# https://www.lanqiao.cn/problems/505/learning/?page=1&first_category_id=1&second_category_id=3
# Date: 2025/2/17
from leetcode import test_function as tf


def get_max_sum_dfs(matrix):
    """我的方法，使用深度优先搜索.
    结果正确，但是一半超时 (5/5 通过/超时)
    时间复杂度为O(V^2)
    """
    max_sum = 0
    n = len(matrix)

    def dfs(depth, idx, left_cnt, right_cnt, s):
        nonlocal max_sum, matrix
        if depth >= n:
            max_sum = max(max_sum, s)
            return

        s += matrix[depth][idx]

        if left_cnt >= n // 2:
            dfs(depth + 1, idx + 1, left_cnt, right_cnt + 1, s)  # 右下
        elif right_cnt >= n // 2:
            dfs(depth + 1, idx, left_cnt + 1, right_cnt, s)  # 左下
        else:
            dfs(depth + 1, idx, left_cnt + 1, right_cnt, s)  # 左下
            dfs(depth + 1, idx + 1, left_cnt, right_cnt + 1, s)  # 右下

    dfs(0, 0, 0, 0, 0)
    return max_sum


def get_max_sum_dp(matrix):
    """实际上由于向左向右的步数已经限制死了, 所以路径的终点节点都是确定的, 路径的终点为:
    n为奇数时: 最后一行的中间位置
    n为偶数时: 最后一行中间的两个元素之一
    以此, 可以由上向下求每个节点的最大值, 最后取终点的值即为最大值
    时间复杂度为O(V)
    """
    n = len(matrix)
    dp = [[0] * i for i in range(1, n + 1)]  # 新建一个三角形矩阵
    dp[0][0] = matrix[0][0]
    for i in range(1, n):  # 逐个遍历每一行
        for j in range(i + 1):  # 求每个节点的最大值
            if j == 0:
                dp[i][j] = dp[i - 1][j] + matrix[i][j]  # 最左边的节点
            elif i == j:
                dp[i][j] = dp[i - 1][j - 1] + matrix[i][j]  # 最右边的节点
            else:
                dp[i][j] = max(dp[i - 1][j - 1] + matrix[i][j], dp[i - 1][j] + matrix[i][j])  # 所有中间的节点

    if n % 2 != 0:  # 奇数行: 中间节点的值
        return dp[n - 1][n // 2]
    else:  # 偶数行: 中间两节点的最大值
        return max(dp[n - 1][n // 2 - 1], dp[n - 1][n // 2])


if __name__ == '__main__':
    # n = int(input())
    # inp = []
    # for i in range(n):
    #     inp.append(list(map(int, input().split())))

    arr = []
    with open("../data/505.in", "r") as file:
        n = int(file.readline())
        for i in range(n):
            arr.append(list(map(int, file.readline().split())))

    inp = [{"matrix": [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]},
           {"matrix": [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5], [1, 1, 1, 1, 1, 1]]},
           {"matrix": arr},
           ]
    out = [27, 31, 6910]
    tf(get_max_sum_dfs, inp[:-1], out[:-1])
    tf(get_max_sum_dp, inp, out)
